#include <stdio.h>
#include <stdlib.h>
 
// 获取数字的指定位数上的数值
// 参数说明：
// num：要获取位数的数字
// digit：指定的位数（从右往左数，个位为第 1 位）
int getDigit(int num, int digit) 
{
    int temp = 1;
    // 通过循环生成指定位数对应的基数（如获取十位，temp 为 10）
    for (int i = 0; i < digit - 1; i++) 
    {
        temp *= 10;
    }
    // 获取指定的数字，并返回该位上的数值
    return (num / temp) % 10;
}
 
// 基数排序函数
// 参数说明：
// arr：待排序的数组
// n：数组的长度
void radixSort(int arr[], int n) 
{
    int maxVal = arr[0];
    // 找出数组中的最大值
    for (int i = 1; i < n; i++) 
    {
        if (arr[i] > maxVal) 
        {
            maxVal = arr[i];
        }
    }
    int maxDigit = 0;
    // 计算最大值的位数
    while (maxVal > 0) 
    {
        maxVal /= 10;
        maxDigit++;
    }
    // 定义一个指针数组，每个指针指向一个整数数组，用于存储不同位数上的数字
    int* buckets[10];
    for (int i = 0; i < 10; i++) 
    {
        // 为每个桶分配内存空间，每个桶可以存储 n 个整数
        buckets[i] = (int*)malloc(n * sizeof(int));
    }
    // 初始化每个桶的大小为 0
    int bucketSizes[10] = {0};
    // 对每一位进行排序
    for (int digit = 1; digit <= maxDigit; digit++) 
        {
        for (int i = 0; i < n; i++) 
        {
            // 获取当前数字在当前位数上的值
            int currentDigit = getDigit(arr[i], digit);
            // 将数字放入对应的桶中，并增加桶的大小
            buckets[currentDigit][bucketSizes[currentDigit]++] = arr[i];
        }
        int index = 0;
        // 将桶中的数字依次取出，放回原数组
        for (int i = 0; i < 10; i++) 
        {
            for (int j = 0; j < bucketSizes[i]; j++) 
            {
                arr[index++] = buckets[i][j];
            }
            // 重置桶的大小为 0，为下一次排序做准备
            bucketSizes[i] = 0;
        }
    }
    // 释放每个桶占用的内存空间
    for (int i = 0; i < 10; i++) 
    {
        free(buckets[i]);
    }
}
 
// 打印数组函数
// 参数说明：
// arr：要打印的数组
// n：数组的长度
void printArray(int arr[], int n) 
{
    for (int i = 0; i < n; i++) 
    {
        // 依次输出数组中的每个元素
        printf("%d ", arr[i]);
    }
    // 输出换行符，使输出更加清晰
    printf("\n");
}
 
int main() 
{
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    // 输出原始数组
    printf("原始数组：");
    printArray(arr, n);
    // 调用基数排序函数对数组进行排序
    radixSort(arr, n);
    // 输出排序后的数组
    printf("排序后的数组：");
    printArray(arr, n);
    return 0;
}